/*
Marcos Haruo Tamegushi - N° USP: 5889582
William Seiji Matsui - N° USP: 6426548
Yuri de Azevedo Machioni - N° USP: 6792857
*/

#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

inline int isPalindrome(char* string){  //retorna 1 se for palindromo, 0 caso contrario
    int i = 0, j = strlen(string)-1;
    for(; i < j; i++, j--)
        if(string[i] != string[j])
            return 0;

    return 1;
}

inline int canBePrime(char* palindrome){  //retorna 1 se tem chance da soma dos ascii ser primo (25%), 0 caso contrario
    int size = strlen(palindrome);
    if(size % 2 == 1 && palindrome[(size/2)] % 2 == 1)
        return 1;
    else return 0;
}

inline int isPrime(char* string){   //soma os ascii e checa se a soma eh primo pelo algoritmo do crivo de eratostenes
    int i, j, size = strlen(string), n = 0;

    for(i = 0; i < size; i++)
        n += (int) string[i];

    for(i = 2; i <= sqrt(n); i++)
        for(j = 2*i; j <= n; j += i)
             if(n == j)
                return 0;

    return 1;
}

char* fileToString(char* filename){  //retorna um ponteiro pro começo da string que contem o texto do arquivo
    long size;
    FILE *f = fopen(filename, "rb");
    char *temp;

    if(f == NULL){
        printf("Erro ao ler arquivo\n");
        return NULL;
    }
    fseek(f, 0, SEEK_END);
    size = ftell(f);
    fseek(f, 0, SEEK_SET);

    temp = (char*) malloc((size+1) * sizeof(char));
    fread(temp, sizeof(char), size, f);
    temp[size] = '\0';
    fclose(f);
    return temp;
}

void printWords(char* word, int id){  //imprime todas as palavras do arquivo. funçao para teste, nao eh chamada.
    int somaAscii = 0, i, size = strlen(word);
    for(i = 0; i < size; i++)
       somaAscii += (int) word[i];
    printf("palavra: %s\n isPalindrome: %d, canBePrime: %d, isPrime: %d somaAscii: %d tid: %d\n\n",
            word, isPalindrome(word), canBePrime(word), isPrime(word), somaAscii, id);
}

int notFoundYet(char* string, char** alreadyFound, long alreadyFoundIndex, long *alreadyFoundCount){ //checa se o palindromo ja foi encontrado antes e incrementa seu contador
    int i;
    for(i = 0; i < alreadyFoundIndex; i++){
        if(!strcmp(string, alreadyFound[i])){
            #pragma omp critical(alreadyFoundCount)
            {
                alreadyFoundCount[i]++;
            }
            return 0;
        }
    }
    #pragma omp critical(alreadyFound)
    {
        alreadyFoundCount[i]++;
    }
    return 1;
}

void printOcurrences(char **alreadyFound, long *alreadyFoundCount, long alreadyFoundIndex){ //imprime quantas vezes um palindromo foi encontrado
    long i, totalPalindromos = 0;
    printf("\n\n");
    for(i = 0; i < alreadyFoundIndex; i++){
        totalPalindromos += alreadyFoundCount[i];
        printf("-palindromo %s encontrado %ld vezes\n", alreadyFound[i], alreadyFoundCount[i]);
    }
    printf("\n---total de palindromos encontrados: %ld\n", totalPalindromos);
    printf("---total de palindromos encontrados (sem repeticao): %ld\n", alreadyFoundIndex);

}

char* porFrases(char* string, long filesize){ //retorna um vetor que eh igual a string, porem sem espaço entre as palavras,
    char *newstring;                           // e com espaco onde havia ponto ou quebra de linha etc.
    char *pNewstring, *ptemp;                 //facilita a decomposicao posteriormente, para busca por frases
    int tempsize;

    newstring = (char*) malloc(filesize * sizeof(char));
    pNewstring = newstring;

    ptemp = strtok(string, " ,!?)(\\\'\""); //quebra as palavras da string se encontrar algum destes caracteres
    strcpy(pNewstring, ptemp);  //adiciona ela na nova string

    while(ptemp != NULL){            //enquanto nao chega no fim da string
        tempsize = strlen(pNewstring);
        pNewstring += tempsize;

        if(*(pNewstring-1) == '.' || *(pNewstring-1) == '\n' || *(pNewstring-1) == ';' || *(pNewstring-1) == ':')
            *(pNewstring-1) = ' '; //checa se a palavra adicionada termina com . ou \n, e substitui por espaço se terminar

        ptemp = strtok(NULL, " ,!?)(\\\'\"");  //pega a proxima palavra
        if(ptemp != NULL)
            strcpy(pNewstring, ptemp);  //adiciona ela na nova string (equivalente e concatenar, pos pNewstring foi incrementada de strlen(palavra)
    }                                   //porem muito mais eficiente que strcat
    return newstring;  //retorna a nova string
}

int main(int argc, char *argv[]){

    char *start, *end, *string; //ponteiro pro inicio e pro fim de um bloco, e a string que ira armazenar todo o texto do arquivo
    long filesize, i, nthreads = 1;
    char *alreadyFound[3000];    //vetor de palindromos ja encontrados
    long alreadyFoundIndex = 0, *alreadyFoundCount;  //indice do vetor de palindromos ja encontrados, contador de quantas vezes cada palindromo foi encontrado
    char **stringStart;  //vetor de ponteiros para inicio de blocos
    char **stringEnd;   //vetor de ponteiros para fins de blocos
    int totalprimes=0;

    if(argc < 3){
        printf("usage: palindromo nthreads file -porfrase(optional)\n\n");
        return 0;
    }
    sscanf(argv[1], "%ld", &nthreads); //seta o numero de threads pelo primeiro argumento da linha de comando
    string = fileToString(argv[2]);  //abre o arquivo e copia seu conteudo pra string
    if(string == NULL || nthreads < 1){
        return 0;
    }

    filesize = strlen(string);

    if(argc == 4 && !strcmp(argv[3], "-porfrase")){
        char *ptemp = string;
        string = porFrases(string, filesize);
        free(ptemp);
        filesize = strlen(string);
    }

    stringStart = (char**) malloc(nthreads * sizeof(char*));  //aloca nthreads blocos (cada um dos quais executara aprox. 1/nthreads da string)
    stringEnd = (char**) malloc(nthreads * sizeof(char*));
    alreadyFoundCount = (long*) calloc(3000, sizeof(long));  //zera os contadores de quantas vezes cada palindromo foi encontrado

    //decomposicao de dados (em blocos 1D)

    start = string;   //comeco do primeiro bloco eh na primeira posicao da string
    for(i = 0; i < nthreads; i++)
    {
        stringStart[i] = start; //comeco do bloco i eh onde start aponta

        end = string + (filesize*(i+1))/nthreads;   //aponta pro fim do bloco (  a ser ajustado )
        while(end < (string + filesize) && isalpha(*end)) // ajusta o fim do bloco caso tenha caido no meio de uma palavra (vai ateh o fim dela)
            end++;
        *end = '\0';  //coloca um \0 depois  da ultima palavra do bloco (equivalente a dividir o arquivo em nthreads strings,
        stringEnd[i] = end;  //sendo que cada elemento de stringStart[] aponta para o começo de um bloco e cada elto de stringEnd aponto para o fim de um bloco
        start = end+1;     //posiciona o inicio do proximo bloco no primeiro caracter valido depois do fim do bloco anterior
        while(start < (string + filesize) && !isalpha(*start))
            start++;
    }

    //inicio da regiao paralela

    #pragma omp parallel for shared(alreadyFound, alreadyFoundIndex, alreadyFoundCount) private(i) num_threads(nthreads)
    for(i = 0; i < nthreads; i++){
        char *currentWordEnd, *currentWord; //ponteiro pro começo e pro fim da palavra sendo processada
        int size, somaAscii = 0, j;
        currentWord = stringStart[i]; //posiciona currentWord no inicio do bloco

        while(currentWord < stringEnd[i]){  //enquanto nao chega no fim do bloco
            currentWordEnd = currentWord;   //posiciona o ponteiro do fim da palavra pro começo dela e

            while(isalpha(*currentWordEnd)) //incrementa ele ateh chegar no fim da palavra
                currentWordEnd++;

            *currentWordEnd = '\0';      //quebra a palavra em uma string nova (apontada por currentWord)
            size = strlen(currentWord);  //calcula o tamanho da palavra

            if(*currentWord == *(currentWordEnd-1) && isPalindrome(currentWord)){   //se a primeira letra for igual a ultima, checa se eh palindromo
                if(notFoundYet(currentWord, alreadyFound, alreadyFoundIndex, alreadyFoundCount)){  //se for palindromo e se nao foi achado antes
                    #pragma omp critical(AlreadyFound)
                    {
                        alreadyFound[alreadyFoundIndex] = currentWord;  //insere palavra atual no final do vetor de ja encontrados
                        alreadyFoundIndex++;
                    }

                    printf("palindromo encontrado pela thread %ld: %s\n", i, currentWord); //imprime palavra, faz soma dos ascii etc
                    for(j = 0; j < size; j++)
                        somaAscii += (int) currentWord[j];
                    if(canBePrime(currentWord)){
                        if(isPrime(currentWord)){
                            totalprimes++;
                            printf("soma dos ascii: %d (primo) \n\n", somaAscii);
                        } else printf("soma dos ascii: %d (nao primo) \n\n", somaAscii);
                    } else printf("soma dos ascii: %d (nao primo) \n\n", somaAscii);

                    somaAscii = 0;
                }
            }

            //printWords(word, i);
            currentWord += size; //adiciona o tamanho desta palavra ao ponteiro (desloca o ponteiro para frente no bloco size+1 posicoes)
            while(currentWord < stringEnd[i] && !isalpha(*currentWord)) //checa se a posicao ja eh o comeco de outra palavra e
                currentWord++;                                                                  //vai deslocando pra frente enquanto nao for.
        }                                                                                       //sai do loop se chegar ao fim do bloco
    }

    printOcurrences(alreadyFound, alreadyFoundCount, alreadyFoundIndex);   //imprime o numero de ocorrencias de cada palindromo
    printf("---total de palindromos com soma dos ascii primo: %d\n", totalprimes);

    free(stringStart);
    free(stringEnd);
    free(alreadyFoundCount);
    free(string);

    return 0;
}
